//
// Created by liushuai on 2021/1/9.
//

#include "coinChange.h"
<<<<<<< HEAD
int dp(vector<int>& coins, int amount, vector<int>& cache)
{
=======
// int coinChange(vector<int>& coins, int amount) {}
int coinChange(vector<int> &coins, int amount) {
    std::vector<int> dp_cache = std::vector<int>(amount + 1, -1);
    dp_cache[0] = 0;
    for (int i = 1; i <= amount; i++) {
        int min_value = std::numeric_limits<int>::max();
        for (auto coin : coins) {
            if (i - coin >= 0 && dp_cache[i - coin] != -1) {
                min_value = dp_cache[i - coin] + 1 > min_value
                                ? min_value
                                : dp_cache[i - coin] + 1;
            }
        }
        dp_cache[i] =
            min_value == std::numeric_limits<int>::max() ? -1 : min_value;
    }
    return dp_cache[amount];
}

int dp(vector<int> &coins, int amount, vector<int> &cache) {
>>>>>>> dev
    if (amount < 0)
        return -1;
    else if (amount == 0)
        return 0;
<<<<<<< HEAD
    else
    {
        if (cache[amount - 1] != 0)
            return cache[amount - 1];
        else
        {
            int result = INT_MAX;
            for (int coin : coins)
            {
                int res = dp(
                    coins, amount - coin, cache); // 选择面额为coin的硬币，意味着结果为 amount-coin的最小硬币是否有解
                if (res >= 0 && res < result)
                { //如果有解，res>=0，获取不同面额硬币结果，保存最小值
=======
    else {
        if (cache[amount - 1] != 0)
            return cache[amount - 1];
        else {
            int result = INT_MAX;
            for (int coin : coins) {
                int res = dp(coins, amount - coin,
                             cache); // 选择面额为coin的硬币，意味着结果为
                                     // amount -coin的最小硬币是否有解
                if (res >= 0 &&
                    res <
                        result) { // 如果有解，res>=0，获取不同面额硬币结果，保存最小值
>>>>>>> dev
                    result = res + 1;
                }
            }
            // 找到最小值，如果result没有更新过，说明选择面额无法拼凑
            cache[amount - 1] = result == INT_MAX ? -1 : result;
            return cache[amount - 1];
        }
    }
}

<<<<<<< HEAD
int coinChange(vector<int>& coins, int amount)
{
    vector<int> cache = vector<int>(amount, 0);
    return dp(coins, amount, cache);
}
int coinChange1(vector<int>& coins, int value)
{
    vector<int> DP = vector<int>(value + 1, -1);
    DP[0] = 0;
    for (int i = 1; i < value + 1; i++)
    {
        int minValue = INT_MAX;
        for (auto coin : coins)
        {
            if (i - coin >= 0 && DP[i - coin] != -1)
            {
                if (DP[i - coin] != -1)
                    minValue = DP[i - coin] + 1 > minValue ? minValue : minValue = DP[i - coin] + 1;
            }
        }
        DP[i] = minValue == INT_MAX ? -1 : minValue;
    }
    return DP[value];
}
int coinChange2(vector<int>& coins,int value)
{
    int count = 0;
    for(auto iter = coins.rbegin();iter!=coins.rend();iter++)
    {
        int curren_money = *iter;
        if(curren_money<=value)
        {
            if(curren_money!=0)
            {
                count += value/curren_money;
                value %= curren_money;
            } else
                break;
        }
    }
    return count;
}
=======
int coinChangeTtoB(vector<int> &coins, int amount) {
    vector<int> cache = vector<int>(amount, 0);
    return dp(coins, amount, cache);
}
// int coinChange1(vector<int>& coins, int value)
// {
//     vector<int> DP = vector<int>(value + 1, -1);
//     DP[0] = 0;
//     for (int i = 1; i < value + 1; i++)
//     {
//         int minValue = INT_MAX;
//         for (auto coin : coins)
//         {
//             if (i - coin >= 0 && DP[i - coin] != -1)
//             {
//                 if (DP[i - coin] != -1)
//                     minValue = DP[i - coin] + 1 > minValue ? minValue :
//                     minValue = DP[i - coin] + 1;
//             }
//         }
//         DP[i] = minValue == INT_MAX ? -1 : minValue;
//     }
//     return DP[value];
// }
// int coinChange2(vector<int>& coins,int value)
// {
//     int count = 0;
//     for(auto iter = coins.rbegin();iter!=coins.rend();iter++)
//     {
//         int curren_money = *iter;
//         if(curren_money<=value)
//         {
//             if(curren_money!=0)
//             {
//                 count += value/curren_money;
//                 value %= curren_money;
//             } else
//                 break;
//         }
//     }
//     return count;
// }
>>>>>>> dev
